package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class FourSum {

  // Working!! O(n^3)
  //time limit
  public static ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
    Arrays.sort(num);
    for(int i=0;i<num.length-3;){
        for(int j=i+1;j<num.length-2;){
            int k=j+1;
            int l=num.length-1;
            while(k<l){
            if(num[i]+num[j]+num[k]+num[l]==target){
                ArrayList<Integer> list =new ArrayList<Integer>();
                list.add(num[i]);
                list.add(num[j]);
                list.add(num[k]);
                list.add(num[l]);
                al.add(list);
                while(k<num.length-1&&num[k]==list.get(2)) k++;
                while(l>2&&num[l]==list.get(3)) l--;
               }
            else if(num[i]+num[j]+num[k]+num[l]<target) k++;
            else l--;
            }
          int jprevious=num[j];
          while(j<num.length-2&&num[j]==jprevious) j++;
          }
       int iprevious=num[i];
       while(i<num.length-3&&num[i]==iprevious) i++;
       }
   return al;     

  }

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    fourSum(new int[] { 1, 0, -1, 0, -2, 2 }, 0);

  }
}
